// Created by WXX on 2021/9/20 19:48
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了51.08%的用户
 * 内存消耗：8.9 MB, 在所有 C++ 提交中击败了5.81%的用户
 */
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> stk;
        vector<int> q(nums2.size());
        for (int i = nums2.size() - 1; i >= 0; i--) {
            int x = nums2[i];
            while (stk.size() && x >= stk.top()) stk.pop();
            if (stk.empty()) q[i] = -1;
            else q[i] = stk.top();
            stk.push(x);
        }

        unordered_map<int, int> hash;
        for (int i = 0; i < nums2.size(); i++) hash[nums2[i]] = i;

        vector<int> res;
        for (auto x : nums1)
            res.push_back(q[hash[x]]);
        return res;
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> nums1 = {4, 1, 2}, nums2 = {1, 3, 4, 2};
    OutputBasicArray1D(Solution().nextGreaterElement(nums1, nums2));

    return 0;
}
